package com.itheima.datastructure.linkedlist;

/**
 * 删除倒数节点
 */
public class E03Leetcode19 {
    /*
    recursion(ListNode p=1, int n=2) {
        recursion(ListNode p=2, int n=2) {
            recursion(ListNode p=3, int n=2) {
                recursion(ListNode p=4, int n=2) {
                    recursion(ListNode p=5, int n=2) {
                        recursion(ListNode p=null, int n=2) {
                            return 0;
                        }
                        return 1;
                    }
                    return 2;
                }
                if(返回值 == n == 2) {
                    删除
                }
                return 3;
            }
            return 4;
        }
        return 5;
    }
    */


    /**
     * 删除链表倒数第几个
     *
     * @param head
     * @param n
     * @return
     */
    ListNode removeNthFromEnd0(ListNode head, int n) {
        int size = getNum(head);
        ListNode sentinel = new ListNode(-1, head);
        ListNode pre = sentinel;
        ListNode cur = head;

        int i = 0;
        while (cur != null) {
            if ((size - i) == n) {
                System.out.printf("删除倒数%d个，值%d \n", n, cur.val);
                pre.next = cur.next;
                cur = pre.next;
                i++;
            } else {
                i++;
                cur = cur.next;
                pre = pre.next;
            }

        }
        return sentinel.next;

    }

    private int getNum(ListNode head) {
        int num = 0;
        while (head != null) {
            num++;
            head = head.next;
        }
        return num;
    }

    // 方法1
    public ListNode removeNthFromEndR(ListNode head, int n) {
        ListNode s = new ListNode(-1, head);
        recursion(s, n);
        return s.next;
    }


    // 方法2 查看当前节点是倒数第几个
    private int recursion(ListNode cur, int n) {
        if (cur == null) {
            return 0;
        }
        //返回下一个节点是倒数第几个
        int nextTh = recursion(cur.next, n);
        if (nextTh == n) { //如果cur.next是倒数第n个，则删除cur.next
            // 删除cur.next
            cur.next = cur.next.next;
        }
        //返回当前节点是倒数第几个,下一个节点的倒数为nextTh,那么当前节点为倒数nextTh+1
        return nextTh + 1;
    }


    /*
        n=2
        p1
        p2
        s -> 1 -> 2 -> 3 -> 4 -> 5 -> null

             p2
        s -> 1 -> 2 -> 3 -> 4 -> 5 -> null

                  p2
        s -> 1 -> 2 -> 3 -> 4 -> 5 -> null

        p1             p2
        s -> 1 -> 2 -> 3 -> 4 -> 5 -> null

                       p1             p2
        s -> 1 -> 2 -> 3 -> 4 -> 5 -> null
     */
    // 方法2
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode sentinel = new ListNode(-1, head);
        // 慢指针
        ListNode slowNode = sentinel;
        // 快指针
        ListNode fastNode = sentinel;
        //移动快指针n步
        for (int i = 0; i <= n; i++) {
            fastNode = fastNode.next;
        }
        //直到快指针到达末尾,慢指针指向的节点就是倒数第n个节点,删除慢指针的下一个节点
        while (fastNode != null) {
            slowNode = slowNode.next;
            fastNode = fastNode.next;
        }
        slowNode.next = slowNode.next.next;
        return sentinel.next;
    }

    public static void main(String[] args) {
        ListNode head = ListNode.of(1, 2, 3, 4, 5);
//        ListNode head = ListNode.of(1,2);
        System.out.println(head);
        System.out.println(new E03Leetcode19()
                .removeNthFromEnd(head, 1));
    }


}
